Modern society and technology are increasingly based on information or data. Data of a wide variety of types is commonly stored or held, accessed or retrieved, and modified or updated. A variety of means are used to perform such operations—means ranging from time-tested paper and ink to state-of-the-art, high-technology electronic circuits.
For example, using a 2003 telephone book that includes Santa Clara, Calif. and looking for “Integrated Silicon Solution, Inc.,” one can find the phone number “(408) 588-0800.” Expressed in the terminology used to describe electronic memories, the telephone book is a content addressable memory (CAM). Finding a phone number is a lookup operation that matches entries held in the CAM with the key of the lookup operation, the key being “Integrated Silicon Solution, Inc.” All entries within the CAM are searched in order to find those whose content matches the key. For this lookup operation, exactly one matching entry is found and the output is the phone number associated with that entry, i.e. “(408) 588-0800.”
FIG. 1a is a functional diagram of the input, output and contents of a first example content addressable memory (CAM) according to the background art. CAM 110 holds binary information, that is, information in the form of bits having one of two values, i.e. “0” or “1.”
Binary CAM 110 includes four rows, each of which has an associated row number 112. Each row holds a data entry 114, which is a binary number; for example, the highest-priority or first row, that is row number 1, holds a data entry with the value of “1010.” Key 120 is a binary value that is input to binary CAM 110. In response to receiving a value for key 120, binary CAM 110 produces a corresponding value for output 130.
FIG. 1b shows four example lookup operations that occur in binary CAM 110. During each lookup operation 140, binary CAM 110 receives an input key value 120, and in response generates an output value 130. In the first example lookup operation, the key value received is “1100” and the output is “3” because row number 3 is the only row whose content matches the key value, that is, is the same as the key value. In the second example lookup operation, the key value received is “1010” and the output is “1.”
Both row number 1 and row number 2 match the key, but row number 1 has priority over row 2 because it has a smaller row number. Entries in a phone book are ordered alphabetically, but entries in electronic CAMs are generally ordered by priority, which is used to determine which of the matching entries to output when more than one entry matches a particular key.
In both the third and fourth example lookup operations, the output of binary CAM 110 is “Invalid” because no rows match either “1011” or “0001”.
In some CAM systems, the row number output from binary CAM 110 is used as an address to be input to a standard memory, that is, a memory that holds data that is retrieved based on the address of the data within the memory. A standard memory could be used in order to hold the phone number, for example, of the entries within the CAM and to output the phone numbers of the 3rd, 1st or 4th entries based on binary CAM 110 outputting “3,” “1” or “4.”
FIG. 2a is a functional diagram of the input, output and contents of a second example content addressable memory (CAM) according to the background art. CAM 210 holds ternary information, that is, information in the form of bits having one of three values, i.e. “0,” “1” or “either 0 or 1.”
Each of the four entries held by ternary CAM 210 includes both data entry 216 and mask entry 218. Data entries 216 held in ternary CAM 210 have the same values as the data entries 116 within binary CAM 110. A bit with the value “1” within a mask entry 218 indicates that the entry held in that row “does not care about” the value of the key for that bit. For example, the entry in row 4 matches either the key value “1000” or the key value “1001”.
FIG. 2b shows four example lookup operations that occur in ternary CAM 210. During each lookup operation 140, ternary CAM 210 receives as input a key value 120, and in response generates an output value 130. The example key values shown in FIG. 2b are the same as in FIG. 1b. 
In the first, second and fourth example lookup operations, the outputs produced by ternary CAM 210 and the rationales for these outputs are unchanged from the example of FIGS. 1a and 1b. 
However, in the third example lookup operation, the output of ternary CAM 210 is “2” because the entry in row number 2 matches either the value “1010” or the value “1011” because mask entry 218 for row 2 is “0001.” This contrasts with binary CAM 110, which had no entry corresponding to a key value of “1011,” and thus had an “Invalid” output.
A lookup process based on matching contents held in a CAM memory often occurs as a data packet is routed across a computer network. In fact, a data packet traveling along a complex network such as the Internet may trigger hundreds of such lookup operations. Computer networks often include switches, hubs, firewalls, gateways, concentrators or routers, which are collectively termed “routers” herein.
Consider an example in which a router receives a data packet containing part of a web page that is to be displayed on a destination computer. The router extracts from the data packet the network address of the destination computer, say for example, “87.134.242.159.” Then the router uses the destination address, or part of the destination address, such as “87.134” or simply “159,” as the key for a lookup operation in a CAM.
For network routing applications, the speed at which a CAM lookup operation occurs is critical. Displaying a single web page may involve tens of thousands of data packets. Hundreds of web page accesses and numerous other information streams may pass through a single router concurrently. It may be reasonable for a person to take a minute to look up a phone number, but a network router should perform many millions of CAM lookup operations each second.
For network routing applications, the flexibility of lookup operations is also critical. Thus, flexible CAM configurations are critical.
As an example of the need for flexibility, some routers use CAM lookup keys other than, or in addition to, the destination network address. Examples of data that may be included in a key include, among others, the type of the data packet, the size of the data packet, or the network address of the source of the data packet.
As another example, the network data stored in the CAM may include a wide variety of types of information. Such information may include, but is not limited to. i) network links outbound from a router over which packets are to be forwarded when addressed to a particular destination, or to a particular group of destinations; ii) priority or quality of network service information associated with a particular destination or packet type; iii) security information or access privileges; and iv) dynamically maintained load information. As yet another example of the need for flexibility, some routers vary as to the open system interconnection (OSI) layer or layers on which they operate.
Computer networks are not the only electronic devices that employ CAMs. Other applications include data storage networks and systems, video processing, computer graphics and data compression.
Some background-art CAM systems offer high speed by implementing lookup operations as actions that occur simultaneously in parallel hardware. However, hardware implementations tend to be relatively inflexible. Other background-art CAM systems offer flexibility by implementing lookup operations as programmable sequences of actions under the control of software or firmware. However, programmable implementations tend to have relatively low performance.